package org.example.Greedy_Algorithm;

import java.util.Arrays;

public class The_maximum_sum_of_arrays_after_K_negations {
    public static void main(String[] args) {
        //K 次取反后最大化的数组和

        //给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
        //选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
        //重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
        //以这种方式修改数组后，返回数组 可能的最大和 。

        int[] nums = {8,-7,-3,-9,1,9,-6,-9,3};
        int k = 8;
        int i = largestSumAfterKNegations(nums, k);
        System.out.println(i);
    }

    //自己思考没有借鉴别人的想法，实在是这道题太简单了，焯
    public static int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0; //数组总和
        boolean flag = false;
        int i;
        for (i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] > 0) {
                break;
            }
            nums[i] = -nums[i];
            k--;
            flag = true;
        }
        if (k!=0){
            if (flag){
                Arrays.sort(nums);
            }
            for (int j = 0; j < k; j++) {
                nums[0] = -nums[0];
            }
        }
        for (int num : nums) {
            sum+=num;
        }
        return sum;
    }
}
